package s6_排序算法.sort5_基数排序;

import s6_排序算法.BaseSort;

import java.util.Arrays;

/**
 * <code>{@link RadixSort}</code>
 * <p>
 * description: RadixSort
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/21 20:37
 *
 *
 * 基数排序
 * 该写法无法支持负数
 */
public class RadixSort extends BaseSort {

    public static void main(String[] args) {
        //int[] arr = data();
        int[] arr = {53,3,542,748,14,214};
        System.out.println(Arrays.toString(arr));
        new RadixSort().asc(arr);
        System.out.println(Arrays.toString(arr));
    }


    @Override
    public void asc(int[] arr) {

        System.out.println("RadixSort-------------------------------");
        long s = System.currentTimeMillis();

        radixSort(arr);

        long e = System.currentTimeMillis();
        System.out.println("RadixSort: " + (e-s) + "ms");

    }

    private void radixSort(int[] arr) {
        // 定义二维数组表示10个桶，每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        // 定义数组表示每个桶的有效数据
        int[] bucketEleCount = new int[10];

        // 获取数组的最大值
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
        }

        int redix = 10;
        int diff = 1;
        int maxLen = (max+"").length();
        while(maxLen > 0) {

            for (int i = 0; i < arr.length; i++) {
                int element = (arr[i] / diff) % redix;
                bucket[element][bucketEleCount[element]] = arr[i];
                bucketEleCount[element]++;
            }

            int index = 0;
            for (int i = 0; i < bucket.length; i++) {
                if(bucketEleCount[i] > 0) {
                    for (int j = 0; j < bucketEleCount[i]; j++) {
                        arr[index] = bucket[i][j];
                        index ++;
                    }
                }
                bucketEleCount[i] = 0;
            }

            diff *= 10;
            maxLen--;
        }
    }
}
